Nan Madol là ngôi đền nghi lễ và chính trị của triều đại Saudeleur, kết hợp là một khu định cư của 25.000 người trên đảo Pohnpei cho đến khoảng năm 1628.[3] Nằm giữa đảo Pohnpei và Temwen, nơi đây có hoạt động của con người ngay từ thế kỷ thứ 1 hoặc thứ 2 sau Công nguyên. Vào thế kỷ thứ 8 hoặc 9, quá trình xây dựng thành phố bắt đầu với việc xây dựng một kiến trúc bằng đá khối cực kỳ đặc biệt vào năm 1180-1200.[6]

Ít có thông tin để kiểm chứng về quá trình xây dựng. Những người bản địa Pohnpei tuyên bố rằng, những người xây dựng Địa điểm khảo cổ Leluh trên đảo Kosrae đã đến Pohnpei để sử dụng kỹ năng và kinh nghiệm xây dựng lên quần thể Nan Madol ấn tượng hơn nhiều. Nhưng định tuổi bằng đồng vị cacbon đã chỉ ra rằng, Nan Madol có trước Leluh và có nhiều khả năng Nan Madol ảnh hưởng đến Leluh.[6]

Theo truyền thuyết của người Pohnpei, Nan Madol được xây dựng bởi hai pháp sư Olisihpa và Olosohpa từ vùng đất Tây Katau huyền thoại hoặc Kanamwayso. Họ lên một chiếc xuồng lớn để tìm một nơi xây dựng một bàn thờ lớn, nơi họ có thể thờ cúng vị thần nông nghiệp Nahnisohn Sahpw. Sau vài lần sai thì họ đã thành công khi xây dựng bàn thờ trên đảo Temwen, nơi họ tiến hành các nghi thức tôn giáo. Trong truyền thuyết, hai người họ đã lượm những phiến đá khổng lồ với sự giúp đỡ của một con rồng bay. Khi Olisihpa chết vì tuổi già, Olosohpa trở thành vua Saudeleur đầu tiên. Olosohpa kết hôn với một người phụ nữ địa phương và sinh ra 12 thế hệ, tạo ra 16 vị vua Saudeleur khác trong dòng họ Dipwilap. Triều đại của họ kết thúc với cuộc lật đổ của Isokelekel, người cũng cư trú tại Nan Madol, mặc dù vậy người kế nhiệm ông sau đó đã từ bỏ Nan Madol.[7][8][9]